{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 654. 最大二叉树\n",
    "给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：\n",
    "\n",
    "    二叉树的根是数组中的最大元素。\n",
    "    左子树是通过数组中最大值左边部分构造出的最大二叉树。\n",
    "    右子树是通过数组中最大值右边部分构造出的最大二叉树。\n",
    "\n",
    "通过给定的数组构建最大二叉树，并且输出这个树的根节点。\n",
    "\n",
    "\n",
    "示例 ：\n",
    "\n",
    "输入：[3,2,1,6,0,5]\n",
    "输出：返回下面这棵树的根节点：\n",
    "\n",
    "      6\n",
    "    /   \\\n",
    "   3     5\n",
    "    \\    / \n",
    "     2  0   \n",
    "       \\\n",
    "        1\n",
    "\n",
    "提示：\n",
    "\n",
    "    给定的数组的大小在 [1, 1000] 之间。\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/maximum-binary-tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Trying:\n",
      "    Solution().test([3,2,1,6,0,5])\n",
      "Expecting:\n",
      "    [6,3,5,null,2,0,null,null,1]\n",
      "**********************************************************************\n",
      "File \"__main__\", line 5, in __main__\n",
      "Failed example:\n",
      "    Solution().test([3,2,1,6,0,5])\n",
      "Expected:\n",
      "    [6,3,5,null,2,0,null,null,1]\n",
      "Got:\n",
      "    6\n",
      "5 items had no tests:\n",
      "    __main__.Solution\n",
      "    __main__.Solution.constructMaximumBinaryTree\n",
      "    __main__.Solution.test\n",
      "    __main__.TreeNode\n",
      "    __main__.TreeNode.__init__\n",
      "**********************************************************************\n",
      "1 items had failures:\n",
      "   1 of   1 in __main__\n",
      "1 tests in 6 items.\n",
      "0 passed and 1 failed.\n",
      "***Test Failed*** 1 failures.\n"
     ]
    }
   ],
   "source": [
    "\"\"\"递归方式求解\n",
    "# Testcase:\n",
    "\n",
    ">>> Solution().test([3,2,1,6,0,5])\n",
    "[6,3,5,null,2,0,null,null,1]\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "#     def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:\n",
    "    def constructMaximumBinaryTree(self, nums):\n",
    "        if not nums:\n",
    "            return\n",
    "        max_num = max(nums)\n",
    "        max_index = nums.index(max_num)\n",
    "        root = TreeNode(max_num)\n",
    "        root.left = self.constructMaximumBinaryTree(nums[:max_index])\n",
    "        root.right = self.constructMaximumBinaryTree(nums[max_index+1:])\n",
    "        return root\n",
    "    \n",
    "    def test(self, nums):\n",
    "        root = self.constructMaximumBinaryTree(nums)\n",
    "        print(self.constructMaximumBinaryTree(nums))\n",
    "if __name__ == \"__main__\":\n",
    "    import doctest\n",
    "    doctest.testmod(verbose=True)\n",
    "           "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 题解\n",
    "\n",
    "要仔细读清楚要求，先找出最大值，然后 left 为左半部分的最大值，right 为其有半部分的最大值；递归求解便于理解。\n",
    "\n",
    "这里有 max_num 标签，分治思想。也可以使用队列和迭代方式。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
